﻿using System;
using System.Collections.Generic;
using System.Text;

namespace GPLib
{
    /// <summary>
    /// Retrieves the user-entered string given a random buffer of characters and the characters captured by a source.  The source must have been 
    /// activated during the entire Garbage Pump process and the source must have been watching for keystrokes the entire time.
    /// </summary>
    internal static class StringDeltaAnalysis
    {

        /*
         * Minimum number of consecutive matches needed for the buffers to be considered synchronized.
         * 
         * The liklihood of a mismatch varies with the number of possible keystrokes.
         * On a standard US keyboard without any modified keys the number would be:
         * 
         * 1/47^MIN_MATCH_DEFAULT 
         * 
         * The default = 1/47^5 = 0.000000004360243163697.
         * 
         * If shift keys are used, then it's:
         * 
         * 1/94^MIN_MATCH_DEFAULT = So very small
         */
        private const int MIN_MATCH_DEFAULT = 5;
        private const bool BACKSPACE_DEFAULT = true;

        /// <summary>
        /// Gets the text that the user entered by synchronizing the buffers and finding the delta between the 
        /// random buffer and the form-based buffer that had the focus when the Garbage Pump was started.
        /// </summary>
        /// <param name="appPresses">The buffer used when monitoring input (usually on a form)</param>
        /// <param name="randomBuffer">The random keystrokes generated by the Garbage Pump</param>
        /// <returns>The user's real text or String.Empty if no text is found or possibly even garbage</returns>
        internal static string GetUserText( List< char > appPresses, List< char > randomBuffer )
        {
            return GetUserText( appPresses, randomBuffer, BACKSPACE_DEFAULT, MIN_MATCH_DEFAULT );
        }

        /// <summary>
        /// Gets the text that the user entered by synchronizing the buffers and finding the delta between the 
        /// random buffer and the form-based buffer that had the focus when the Garbage Pump was started.
        /// </summary>
        /// <param name="appPresses">The buffer used when monitoring input (usually on a form)</param>
        /// <param name="randomBuffer">The random keystrokes generated by the Garbage Pump</param>
        /// <param name="handleBackspaces">True to let backspaces remove the previous character, False to leave backspaces as part of the string.</param>
        /// <returns>The user's real text or String.Empty if no text is found or possibly even garbage</returns>
        internal static string GetUserText( List< char > appPresses, List< char > randomBuffer, bool handleBackspaces )
        {
            return GetUserText( appPresses, randomBuffer, handleBackspaces, MIN_MATCH_DEFAULT );
        }

        /// <summary>
        /// Gets the text that the user entered by synchronizing the buffers and finding the delta between the 
        /// random buffer and the form-based buffer that had the focus when the Garbage Pump was started.
        /// </summary>
        /// <param name="appPresses">The buffer used when monitoring input (usually on a form)</param>
        /// <param name="randomBuffer">The random keystrokes generated by the Garbage Pump</param>
        /// <param name="handleBackspaces">True to let backspaces remove the previous character, False to leave backspaces as part of the string.</param>
        /// <param name="minimumMatchesRequired">Minimum matches needed in order to definitively state the buffers are synchronized.  
        ///                                      This should be a small enough number so as to not exceed where the first user keystroke was entered or else
        ///                                      Garbage or String.Empty will be returned.</param>
        /// <returns>The user's real text or String.Empty if no text is found or possibly even garbage</returns>
        internal static string GetUserText( List< char > appPresses, List< char > randomBuffer, bool handleBackspaces, int minimumMatchesRequired )
        {

            if ( appPresses.Count - randomBuffer.Count <= 0 || randomBuffer.Count == 0 )
                return String.Empty;

            StringBuilder sb = new StringBuilder( appPresses.Count - randomBuffer.Count );

            //Synchronize the buffers positions
            int initialoffset = GetInitialBufferOffset( appPresses, randomBuffer, minimumMatchesRequired );

            if ( initialoffset >= appPresses.Count )
                return string.Empty;

            for ( int i = initialoffset, y = 0;
                  i < randomBuffer.Count && y < appPresses.Count;
                  i++, y++ )
            {

                //If they're not equal then there's a user key
                if ( appPresses[ y ] != randomBuffer[ i ] )
                {
                    sb.Append( appPresses[ y ] );
                    //let appPresses move to the next but keep the randombuffer 
                    //at the same position for the next comparison
                    i--;
                }

            }

            return ( handleBackspaces ? GetCorrectString( sb ) : sb.ToString() );

        }


        /// <summary>
        /// A debug complement to GetUserText.
        /// </summary>
        /// <param name="appPresses"></param>
        /// <param name="randomBuffer"></param>
        /// <param name="handleBackspaces"></param>
        /// <param name="minimumMatchesRequired"></param>
        /// <returns></returns>
        internal static List< int > GetUserTextPositions( List< char > appPresses, List< char > randomBuffer, bool handleBackspaces, int minimumMatchesRequired )
        {

            if ( appPresses.Count - randomBuffer.Count <= 0 || randomBuffer.Count == 0 )
                return new List< int >( 0 );

            List< int > positions = new List< int >( appPresses.Count - randomBuffer.Count );

            //Synchronize the buffers positions
            int initialoffset = GetInitialBufferOffset( appPresses, randomBuffer, minimumMatchesRequired );

            if ( initialoffset >= appPresses.Count )
                return positions;

            for ( int i = initialoffset, y = 0;
                  i < randomBuffer.Count && y < appPresses.Count;
                  i++, y++ )
            {

                //If they're not equal then there's a user key
                if ( appPresses[ y ] != randomBuffer[ i ] )
                {
                    positions.Add( y );
                    //let appPresses move to the next but keep the randombuffer 
                    //at the same position for the next comparison
                    i--;
                }

            }

            return positions;
        }

        /// <summary>
        /// Handles backspaces and deletes in order to provide the String the user meant to enter.
        /// </summary>
        /// <param name="sb"></param>
        /// <returns>Corrected string</returns>
        private static string GetCorrectString( StringBuilder sb )
        {

            Stack< char > charstack = new Stack< char >( sb.Length );

            for ( int i = 0; i < sb.Length; i++ )
            {

                if ( sb[ i ] == 0x8 )
                {
                    if ( charstack.Count > 0 )
                        charstack.Pop(); //pop the previous char off the stack (if there is one)
                }
                else
                    charstack.Push( sb[ i ] );
            }

            int stackheight = charstack.Count;

            char[] sb2 = new char[ stackheight ];

            for ( int i = stackheight - 1; i >= 0; i-- )
                sb2[ i ] = charstack.Pop();

            return new string( sb2 );

        }

        /// <summary>
        /// Synchronizes the random buffer to the appPresses buffer.  There are usually a few characters that appear in the appPresses 
        /// before 
        /// </summary>
        /// <param name="appPresses"></param>
        /// <param name="randomBuffer"></param>
        /// <param name="minMatchNeeded"></param>
        /// <returns></returns>
        private static int GetInitialBufferOffset( List< char > appPresses, List< char > randomBuffer, int minMatchNeeded )
        {

            int i = 0;

            bool validEnough = false;

            /*
             * It might be a fluke that there's a match, which can cause garbage to spew back out during the character delta analysis.
             * This is especially the case when the user takes his/her time entering in a password.  The minMatchNeeded
             * is provided to determine how many characters must match in a row before the randomBuffer is considered synchronized.
             */

            int y = 0;

            while ( !validEnough && randomBuffer.Count < y )
            {

                while ( randomBuffer[ i ] != appPresses[ 0 ] && i < randomBuffer.Count )
                    ++i;

                //Ensure the randomBuffer isn't preliminarily exhausted in the synchronization process.
                if ( randomBuffer.Count <= ( i + minMatchNeeded ) )
                    break;

                //Check whether it's valid enough to be considered synchronized.
                validEnough = NextSequenceMatches( appPresses, randomBuffer, i, minMatchNeeded );

                ++y; //shouldn't loop more than the randomBuffer size

            }

            return i;

        }

        /// <summary>
        /// A helper method to employ the logic in GetInitialBufferOffset
        /// </summary>
        /// <param name="appPresses"></param>
        /// <param name="randomBuffer"></param>
        /// <param name="randomBufferOffset"></param>
        /// <param name="minMatchNeeded"></param>
        /// <returns>True if successful</returns>
        private static bool NextSequenceMatches( List< char > appPresses, List< char > randomBuffer, int randomBufferOffset, int minMatchNeeded )
        {

            for ( int i = randomBufferOffset, y = 0;
                  i < ( randomBufferOffset + minMatchNeeded );
                  i++, y++ )
            {
                if ( appPresses[ y ] != randomBuffer[ i ] )
                    return false;
            }

            return true;

        }

    }

}
